Polygonal surfaces form one of the major representations of three dimensional geometric models. Such surfaces consist of a plurality of polygons, which are cycles of vertices, whose coordinates are usually expressed in a local coordinate system. Such polygonal surfaces may be used for generating various images, pictures, and animations, and may also be used in CAD systems, in scientific visualization systems, and in medical imaging systems.
In general, polyhedral surfaces, such as surfaces represented as triangles, are commonly represented in a computer memory with a "vertex array" (with three floating point numbers per vertex) and a "triangle array" (with three indices into the vertex array per triangle). Very often this representation allows for the surface to be non-manifold, i.e., to have singular vertices and edges. A vertex is singular if its star (the set of triangles incident to the vertex) is not topologically equivalent (continuously deformed) to a closed disk. An edge is singular if it is shared by more than two triangles. However, many geometric algorithms and operations, such as compression, simplification, smoothing, and deformation operations, require the surface to be manifold.
There are a number of known algorithms that operate on polygonal surfaces including, but not limited to, the following.
(A) A first type of algorithms are those that produce two dimensional graphics for display on computer screens, for printing, or for other purposes. These algorithms are typically implemented using both software and hardware components.
(B) A second type of algorithms are those that compute surface characteristics (e.g. curvature, area).
(C) A third type of algorithms are those used for filtering, such as smoothing algorithms and other filtering algorithms.
(D) A fourth type of algorithms are those that perform finite element analysis for various engineering applications.
(E) A fifth type of algorithms are those that simplify surfaces, either because the surfaces are too large for current hardware to process in a reasonable period of time, or for efficiency purposes. In this context "simplifying" means approximating the surface with another surface that contains fewer polygons. An example of such a simplification algorithm is described in commonly assigned U.S. Patent Application entitled "Surface Simplification Preserving a Solid Volume and Respecting Distance Tolerances", Ser. No. 08/742,641, filed Nov. 1, 1996, by Andre P. Gueziec.
(F) A sixth type of algorithms are those used for surface subdivision, wherein surface subdivision is considered to be a technique for introducing new polygons into the surface so as to produce a result that resembles a smooth surface.
(G) A seventh type of algorithms are those used for surface compression, wherein surface compression is considered to be a technique to provide an efficient encoding of polygons defining the surface. An example of a surface compression algorithm is described in commonly assigned U.S. Patent Application entitled "Compression of Simple Geometric Models Using Spanning Trees", Ser. No. 08/688,572, filed Jul. 30, 1996, by Jarek J. R. Rossignac and Gabriel Taubin.
Most available algorithms of the foregoing categories, with the exception of the first category (A), require that the surface be a manifold surface. To understand the concept of a manifold surface one can consider a solid object, and the surface bounding that solid object. The bounding surface is a manifold surface, together with surfaces obtained after cutting a series of holes in the original surface. A precise definition of a surface, and of a manifold surface, are given below.
The following three situations can arise when an algorithm that requires that the surface be a manifold surface is instead presented with a surface that is not a manifold surface.
(A) The algorithm can include a method for rejecting the presented surface. However, there is an additional cost incurred in designing and implementing the input surface rejection method.
(B) The algorithm may not recognize that the presented surface is a non-manifold surface, but safeguards allow the computer program implementing the algorithm to terminate properly, without performing the original function of the algorithm. In this case there is an additional cost incurred in designing and implementing the safeguards.
(C) Finally, the computer program implementing the algorithm may simply terminate abnormally. This latter case is undesirable for a number of reasons.
Conventional methods for converting non-manifold surfaces to manifold surfaces include three techniques, described by Szeliski et al. "Curvature and Continuity Control in Particle-Based Surface Models", Proceedings of SPIE "Geometric Methods in Computer Vision II", Vol 2031-15, July 1993, pp.172-181, by Welch and Witkin "Free-Form Shape Design Using Triangulated Surfaces", Proceedings of ACM SIGGRAPH'95, July 1994, pp.247-256, and by Butlin et al. "CAD Data Repair", in 5th International Meshing Roundtable, Pittsburgh, Pa., October 1996.
The technique of Szeliski et al. builds a new polygonal surface from an existing surface by defining a collection of point samples, using point repulsion methods to distribute the points evenly. Subsequently, a surface triangulation of the remaining points is found by extending the techniques of Delaunay triangulations to surfaces. Delaunay triangulations are discussed by O'Rourke in "Computational geometry in C", Cambridge University Press, 1994. The method of Szeliski et al. produces surfaces that are manifolds, but at the expense of discarding the original surface geometry (vertex positions) and connectivity (triangles or polygons), by defining entirely new vertices and triangles. Furthermore, the triangulation method employed is a heuristic method that most likely does not apply in all cases.
The technique of Welch et al. builds a polygonal surface starting from a simple surface, by applying a series of surface operations that consist of adding, deleting, or morphing a portion of the surface. This technique uses methods similar to Szeliski et al. for building triangulations of the surface points. Surface or mesh cutting techniques are also used, but the mesh cutting techniques cut only along simple curves, and are not capable of multiplying vertices at complex curve intersections.
The technique of Butlin et al. is directed towards the conversion of CAD data. This technique is interactive and requires user assistance, and automatic methods for detecting and converting vertices where non-manifold situations occur are not described.
None of the prior art techniques known to the inventors solve the problem of the automatic conversion of a non-manifold surface to a manifold surface. The first two conventional techniques modify the surface vertices and polygons. However, the goal should be to convert the surface while maintaining the vertex coordinates and attributes. Another goal should be to perform the conversion automatically, which is not achieved by the third above-referenced technique.
There is thus a long felt need to overcome these and other problems of the prior art and to provide an efficient and automatic conversion of non-manifold polyhedral surfaces to manifold polyhedral surfaces.